package com.coder.algorithm.offer_2;

import com.coder.algorithm.struct.ListNode;

import java.util.Locale;

/**
 * 链表中倒数第 k 个节点
 *
 * @author yuhushuan
 * @date 2020/6/17 23:49
 */
public class _22_1_KthNodeFromEnd {
    private static ListNode findKthToTail(ListNode head, int k) {
        if (head == null || k == 0) {
            return null;
        }
        ListNode start = head, end = head;
        for (int i = 1; i < k; ++i) {
            if (start.getNext() != null) {
                start = start.getNext();
            } else {
                return null;
            }
        }
        while (start.getNext() != null) {
            start = start.getNext();
            end = end.getNext();
        }
        return end;
    }

    public static void main(String[] args) {
        ListNode head = ListNode.Companion.create(new int[] {1,2,3,4,5,6});

        // 功能测试
        // 第 k 个节点在链表的中间；
        print(head, 3);

        // 在链表的头节点
        print(head, 6);

        // 在链表的尾节点
        print(head, 1);

        // 特殊测试
        // null
        print(null, 2);
        // 链表的节点数小于 k
        print(head, 7);
        // k = 0
        print(head, 0);

    }

    private static void print(ListNode head, int k) {
        ListNode result = findKthToTail(head, k);
        System.out.println(String.format(Locale.getDefault(),
                "链表：\n%s\n倒数第 %d 值为 %s", head, k, result == null ? "null" : result.getValue()));
        System.out.println();
    }
}
